//24 Swap Nodes in Pairs
/*
给定一个链表，交换每个相邻的一对节点

Input: 1->2->3->4
Output: 2->1->4->3

*/

//
ListNode *swapPairs(ListNode *head)
{
	ListNode *p = head, *s;

	//
	if (p && p->next)
	{
		s = p->next;
		p->next = s->next; //
		s->next = p;
		head = s;//

		//
		while (p->next && p->next->next)
		{
			s = p->next->next;
			p->next->next = s->next;
			s->next = p->next;
			p->next = s;
			p = s->next;
		}
	}
	return head;
}

//递归解法
class Solution
{
public:
	ListNode *swapPairs(ListNode *head)
	{
		if (head == nullptr || head->next == nullptr)
		{
			return head;
		}
		ListNode *newHead = head->next;
		head->next = swapPairs(newHead->next);
		newHead->next = head;
		return newHead;
	}
};

//官方迭代
class Solution
{
public:
	ListNode *swapPairs(ListNode *head)
	{
		ListNode *dummyHead = new ListNode(0);
		dummyHead->next = head;
		ListNode *temp = dummyHead;
		while (temp->next != nullptr && temp->next->next != nullptr)
		{
			ListNode *node1 = temp->next;
			ListNode *node2 = temp->next->next;
			temp->next = node2;
			node1->next = node2->next;
			node2->next = node1;
			temp = node1;
		}
		return dummyHead->next;
	}
};
